package com.ztom.top100;

/**
 * 乘积最大子数组
 * <p>
 * https://leetcode-cn.com/problems/maximum-product-subarray/
 *
 * @author ZhangTao
 */
public class Code54MaxProduct {

    public int maxProduct2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        return process(nums, nums.length - 1).res;
    }

    /**
     * 以 i 位置结尾的子数组乘积最大
     * 考虑负数的存在:
     * 每个位置需要考虑三者最大: 当前值, 前最大值 * 当前值, 前最小值 * 当前值
     *
     * @param nums
     * @param i
     * @return
     */
    private Info process(int[] nums, int i) {
        if (i == 0) {
            // 以 0 位置结尾
            return new Info(nums[0], nums[0], nums[0]);
        }
        // 前一个位置的信息
        Info info = process(nums, i - 1);
        // 当前的数可产生的最小值
        int min = Math.min(Math.min(nums[i], nums[i] * info.max), nums[i] * info.min);
        // 当前的数可产生的最大值
        int max = Math.max(Math.max(nums[i], nums[i] * info.max), nums[i] * info.min);
        return new Info(min, max, Math.max(info.res, max));
    }

    public class Info {
        private int min;
        private int max;
        private int res;

        public Info(int min, int max, int res) {
            this.min = min;
            this.max = max;
            this.res = res;
        }
    }

    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // 0 位置信息
        int min = nums[0];
        int max = nums[0];
        int res = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // 上一位置信息
            int lmin = min, lmax = max;
            min = Math.min(Math.min(nums[i], lmin * nums[i]), lmax * nums[i]);
            max = Math.max(Math.max(nums[i], lmin * nums[i]), lmax * nums[i]);
            res = Math.max(res, max);
        }
        return res;
    }
}
